package com.yvon.service.demo.algorithm.offer;

/**
 * 调整数组顺序使奇数位于偶数前面
 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9821.%20%E8%B0%83%E6%95%B4%E6%95%B0%E7%BB%84%E9%A1%BA%E5%BA%8F%E4%BD%BF%E5%A5%87%E6%95%B0%E4%BD%8D%E4%BA%8E%E5%81%B6%E6%95%B0%E5%89%8D%E9%9D%A2/README
 */
public class P21 {
    public static void main(String[] args) {
        Solution solution = new P21().new Solution();
        int[] num = new int[]{1,2,3,4,5,6};
        int[] exchange = solution.exchange(num);
        for (int i = 0; i < exchange.length; i++) {
            System.out.print(exchange[i] + " ");
        }
    }

    class Solution {
        public int[] exchange(int[] nums) {
            int p = 0;
            int q = nums.length - 1;
            while (p < q) {
                // 若左指针为 奇数，则左指针往右移动。
                if ((nums[p] & 1) == 1) {
                    ++p;
                    continue;
                }
                // 若右指针为 奇数，则右指针往左移动。
                if ((nums[q] & 1) == 0) {
                    --q;
                    continue;
                }
                // 若左指针为偶数，右指针有奇数，进行交换
                swap(nums, p, q);
            }
            return nums;
        }

        private void swap(int[] nums, int p, int q) {
            int t = nums[p];
            nums[p] = nums[q];
            nums[q] = t;
        }
    }
}
